package com.algorithm4;


import java.util.Arrays;

public class MergeSort {

    public static int[] mergeSort(int[] array){
        if(array.length==1)
            return array;
        int q = (0+array.length)/2;
        int[] left = Arrays.copyOfRange(array,0,q);
        int[] right = Arrays.copyOfRange(array,q,array.length);
        return merge(mergeSort(left),mergeSort(right));
    }

    public static int[] merge(int[] left,int[] right){
        int[] temp = new int[left.length+right.length];
        int k =0;
        int i = 0;
        int j = 0;
        int leftS=left.length;
        int rightS=right.length;
        while((0<=i && i<leftS )&&(0<=j && j<rightS)){
            if(left[i]<right[j]){
                temp[k] = left[i];
                i++;k++;
            }else{
                temp[k] = right[j];
                j++;k++;
            }
        }
        if(i==leftS){
            while(rightS!=j){
                temp[k++] = right[j++];
            }
        }
        if(j==rightS){
            while(leftS!=i){
                temp[k++] = left[i++];
            }
        }
        System.out.println("left:"+Arrays.toString(left)+"-->right:"+Arrays.toString(right)+">>result:"+Arrays.toString(temp));

        return temp;
    }

    public static void swap(int[] array,int i,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    public static void main(String[] args){
        int[] array = new int[]{0,8, 9, 3,10, 2, 4, 5, 6, 7, 1};
        int[] rest = mergeSort(array);
        System.out.println("排序完数据:"+ Arrays.toString(rest));
    }
}
